package com.vincent.algorithms.sort;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 插入排序：工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
 * 插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，
 * 需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间
 *
 * 平均时间复杂度 O(n^2)
 * 最好情况时间复杂度 O(n) (即 数组本来就是升序)
 * 最坏情况时间复杂度 1+2+..n-1   记为 O(n^2) (即 数组本来就是降序)
 * 空间复杂度 O(1)
 * 稳定性 稳定
 * Created by yangwenchang on 2017/8/22.
 */
public class InsertSort implements Sort {
    @Override
    public <T> void sort(T[] array, Comparator<? super T> c) {
        int swapCount = 0;
        int compareCount = 0;

//        默认第一个数据时有序的 然后从第二数据开始往前插入
        for (int i = 1; i < array.length; i++) {
//            依次和前面的数据比较  若前面的数据大于 当前数据时 互换位置
            for (int j = i; j > 0; j--) {
                compareCount++;
                if (c.compare(array[j - 1], array[j]) > 0) {
                    swapCount++;
                    Sort.swap(array, j - 1, j);
                }
//                这里加个短路操作应该是可以  因为前面是有序的  假如不比最后一个数据小时 肯定也不会比之前的小 可以直接断定 不用继续往前比较了
                else {
                    break;
                }

            }
        }

        System.out.println("总计交换次数:" + swapCount);
        System.out.println("总计比对次数:" + compareCount);
    }

    public <T> void sort2(T[] array, Comparator<? super T> c){

        for (int i = 1; i < array.length; i++) {
//            依次和前面的数据比较  若前面的数据大于 当前数据时 互换位置
            for (int j = i; j > 0 && c.compare(array[j - 1], array[j]) > 0; j--) {
//                交换取代后移 不用使用范围更大的temp变量
                Sort.swap(array, j - 1, j);
            }
        }

    }
    public <T> void sort3(T[] array, Comparator<? super T> c){

        for (int i = 1; i < array.length && c.compare(array[i-1],array[i])>0; i++) {
            T temp = array[i];
//            依次和前面的数据比较  若前面的数据大于 当前数据时 互换位置
            int j = i;
            for (;j > 0 && c.compare(array[j - 1], temp) > 0; j--) {
//               后移操作
                array[j] = array[j-1];
            }
            array[j-1] = temp;
        }

    }

    public static void main(String[] args) {

        Integer[] arr = {1,3,5,4,0};
        System.out.println(Arrays.asList(arr));
        new InsertSort().sort(arr,(x,y)->x-y);
        System.out.println(Arrays.asList(arr));
    }
}
